package com.cat.chapter041;

/**
 * @author cat
 * @description https://leetcode.cn/problems/nth-magical-number/description/
 * @create 2025/7/10 14:50
 * @since JDK17
 */

public class Solution02 {
    final int MOD = ((int) (1e9 + 7));
    public int nthMagicalNumber(int n, int a, int b) {
        long l = 1, r = (long) n * Math.min(a, b) + 1, mid;
        while (l + 1 < r) {
            mid = (l + r) / 2;
            long flag = f(a, b, mid, n);
            if (flag > 0) {
                r = mid;
            } else if (flag < 0) {
                l = mid;
            } else {
                return ((int) (mid % MOD));
            }
        }
        return -1;
    }
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    long lcm(int a, int b) {
        return (long) a / gcd(a, b) * b;
    }

    long f(int a, int b, long x, int n) {
        long ans = (x / a + x / b - x / lcm(a, b)) - n;
        if (ans == 0) {
            return (x % a == 0 || x % b == 0) ? 0 : 1;
        }
        return ans;
    }
    public static void main(String[] args) {
        System.out.println(new Solution02().nthMagicalNumber(1000000000, 40000, 40000));
    }
}
